package com.monkeyboy.list;

import com.monkeyboy.ListNode;

/**
 * 合并两个排序的链表
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 * {1,3,5},{2,4,6} --> {1,2,3,4,5,6}
 *
 * @Author Gavin
 * @date 2021.04.05 10:10
 */
public class List07 {
    /**
     * 第一种方法就是普通的迭代，让两个链表的每个节点负责比较,然后分别放入一个新的链表里面
     */
    public ListNode mergeListNode(ListNode p1, ListNode p2) {
        ListNode head = new ListNode();
        ListNode curr = head;
        /**
         * 临界值，就是p1和p2任何一方循环完毕就可以了
         */
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                curr.next = p1;
                p1 = p1.next;
            } else {
                curr.next = p2;
                p2 = p2.next;
            }
            curr = curr.next;
        }
        if (p1 != null) {
            curr.next = p1.next;
        }
        if (p2 != null) {
            curr.next = p2.next;
        }

        return head.next;
    }

    //第二种方法，采用递归的方式
    public ListNode mergeListNode02(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if (p1.val <= p2.val) {
            p1.next = mergeListNode02(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeListNode02(p1, p2.next);
            return p2;
        }
    }

    public static void main(String[] args) {

    }
}
